package algorithm.moore_select;

import java.util.ArrayList;
import java.util.List;

/**
 * 摩尔投票法解决众数类问题
 *     // 摩尔投票法，分为投票阶段和计数阶段，投票阶段当某个count = 0，更换候选人
 *     // 计数阶段统计两个候选人的票数
 *     // 如果至多选取一个候选人，则他的票数一定要 >= n / 2
 *     // 如果至多选取两个候选人，则他的票数一定要 >= n / 3
 *     // 如果至多选取m个候选人，则他的票数一定要 >= n / (m + 1)
 * @author yuisama
 * @date 2022/04/12 17:10
 **/
public class Num229_MajorityElement {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        // 候选人1
        int can1 = nums[0],count1 = 0;
        // 候选人2
        int can2 = nums[0],count2 = 0;
        // 投票阶段
        for (int i : nums) {
            if (i == can1) {
                count1 ++;
                continue;
            }
            if (i == can2) {
                count2 ++;
                continue;
            }
            if (count1 == 0) {
                can1 = i;
                count1 ++;
                continue;
            }
            if (count2 == 0) {
                can2 = i;
                count2 ++;
                continue;
            }
            // 此时既不是候选人1也不是候选人2，两者票数都--
            count1 --;
            count2 --;
        }
        // 计数阶段,统计两个候选人的得票
        count1 = count2 = 0;
        for (int i : nums) {
            if (i == can1) count1 ++;
                // 这里使用else if，避免两个候选人相同，票数统计两次的情况
            else if (i == can2) count2 ++;
        }
        if (count1 > (nums.length) / 3) {
            ret.add(can1);
        }
        if (count2 > (nums.length) / 3) {
            ret.add(can2);
        }
        return ret;
    }
}